/*
 * Balanced Binary Tree
Given a binary tree, determine if it is height-balanced.

For this problem, a height-balanced binary tree is defined as a binary tree in which the depth of the two subtrees of every node never differ by more than 1.
 */
package com.xinpan.exercise;

public class BalancedBinaryTree {
    public boolean isBalanced(TreeNode root) 
    {
        // Start typing your Java solution below
        // DO NOT write main() function
        int left = testBranch(root.left);
        if(left == -1)
            return false;
        int right = testBranch(root.right);
        if(right == -1)
            return false;
        
        if(Math.abs(left - right) > 1)
            return false;
        return true;
    }
    
    public int testBranch(TreeNode root)
    {
        if(root == null)
            return 0;
        
        int left = testBranch(root.left);
        if(left == -1)
            return -1;
        int right = testBranch(root.right);
        if(right == -1)
            return -1;
            
        if(Math.abs(left - right) > 1)
            return -1;
        
        return Math.max(left, right) + 1;
    }
}

class TreeNode {
     int val;
     TreeNode left;
     TreeNode right;
     TreeNode(int x) { val = x; }
 }
